//折半查找

#pragma once

//用折半查找方法，在有序数组 a[n] 中查找 x
//若找到返回下标，否则返回 -1
template <typename E>
int BinarySearch(E a[], int n, E x)
{
    int low = 0;
    int high = n - 1;
    while (low <= high)
    {
        //在 a[low..high] 子序列中折半查找
        int min = (low + high) / 2;
        if (x == a[mid])
            return mid;
        else if (x < a[mid])
            high = mid - 1;
        else
            low = mid + 1;
    }

    return -1; //not found
}

//用折半查找方法(递归)，在有序序列 a[low..high] 中查找 x
//若找到返回下标，否则返回 -1
template<typename E>
int BinarySearch(a[], low, high, E x)
{
    //当待查找序列 a[low..high] 为空时，找不到 x
    if(low > high) //序列为空
        return -1; //not found
    
    int mid = (low + high) / 2;
    if(x == a[mid])
        return mid;
    else if(x < a[mid])
        return BinarySearch(a, low, mid - 1, x);
    else 
        return BinarySearch(a, mid + 1, high, x);
}